Today’s Agenda

  • Hausdorff Distance
  • Gromov–Hausdorff Distance

The Hausdorff Distance

Definition 1 (Directed Hausdorff Distance) For two subsets compact \(X,Y\subset\mathbb R^n\), their Hausdorff distance is \[ \vec{d}_H(X,Y)=\max_{x\in X}\min_{y\in Y}\|x-y\|. \]

Definition 2 (Hausdorff Distance) \[ d_H(X,Y)=\max\bigg\{\vec{d}_H(X,Y),\vec{d}_H(Y,X)\bigg\}. \]

Why Only Euclidean Subsets?

Definition 3 (Hausdorff Distance) Let \((Z,d)\) be a metric space and \(A, B\subset\) compact subsets. \[ \vec{d}^Z_H(A,B)=\max_{a\in A}\min_{b\in B}d(a, b). \]

\[ d^Z_H(A,B)=\max\bigg\{\vec{d}^Z_H(A,B),\vec{d}^Z_H(B,A)\bigg\}. \]

Image of a circle with sample

The Gromov–Hausdorff Distance

  • What if the subsets \(X,Y\) have no common embeddding?

Isometric Embedding

Definition 4 (The Gromov–Hausdorff Distance) The Gromov–Hausdorff distance is defined by \[ d_{GH}(X,Y)=\inf d^Z(f(X),g(Y)), \] over all isometries \(f,g\) and common embeddeding space \((Z,d)\).

  • \(d_{GH}(A,B)=\) if and only if \(A\), \(B\) are isometric.
  • If finite \(|X|=|Y|=n\)
    • Computationally feasible (distortion definition)
    • Exponential

Hausdorff vs Gromov–Hausdorff

  • \((Z,d)\) is a metric space
  • \(X\) is a subset
  • \((X,d)\) is also a metric space

Non-Trivial Lower Bounds

  • \(\frac{1}{2}|diam(X)-diam(Y)|\leq d_{GH}(X,Y)\leq \frac{1}{2}\max\{diam(X), diam(Y)\}\).

  • Bad News

For any \(\varepsilon>0\), there exists a compact metric space \(Z\) and a subset \(X\subseteq Z\) with \(d_{GH}(X,Z) < \varepsilon \cdot d_{H}(X,Z).\)

Closed Riemannian Manifolds

Example using Non-Dense subsets of Circle

  • Our goal is to find lower bounds in terms of the Hausdorff distance.

  • The natural intuition is when a sample becomes dense enough, it starts to capture the geometry of the space.

Need pictures here.

The Curious Case of the Circle

Theorem 1 (2023) For \(X\subset S^1\) with \(d_H(X,S^1)<\frac{\pi}{6}\), then \(d_{GH}(X,S^1)=d_H(X,S^1)\).

  • Is \(\frac{\pi}{6}\) optimal?

Theorem 2 (2024) For \(X\subset S^1\) with \(d_H(X,S^1)<\frac{\pi}{3}\), then \(d_{GH}(X,S^1)=d_H(X,S^1)\).

  • The constant \(\frac{\pi}{3}\) is, indeed, optimal.

  • Picture here.

Theorem 3 (Two Subsets of the Cirlce) For \(X,Y\subset S^1\) with \(d_H(X,S^1)<\frac{\pi}{3}\), then \(d_{GH}(X,S^1)\geq d_H(X,S^1)\).

Metric Graphs

Questions

Thank you